#include <string>
#include <algorithm>
#include "defines.h"
#include "interpreter.h"
#include "transition.h"
#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include "boost/function.hpp" 
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/construct.hpp>
#include <boost/lambda/bind.hpp>

//#include <boost/bind.hpp>
#include "log4cxx/logger.h"
#include "log4cxx/basicconfigurator.h"
#include "log4cxx/helpers/exception.h"
using namespace log4cxx;
using namespace log4cxx::helpers;

#define ATTR_VALUE(node, attr) ((node).attribute(attr).value())
using namespace std;

LoggerPtr    logger(Logger::getLogger("MyApp"));


const char* node_types[] =
{
    "null", "document", "element", "pcdata", "cdata", 
    "comment", "pi", "declaration"
};

struct simple_walker: pugi::xml_tree_walker
{
    virtual bool for_each(pugi::xml_node& node)
	{
	    for (int i = 0; i < depth(); ++i) std::cout << "  "; // indentation
	    
	    std::cout << node_types[node.type()] << ": name='" 
		      << node.name() << "', value='" << node.value() << "'\n";

	    return true; // continue traversal
	}
};

Interpreter::Interpreter() :
    m_root(new State("__root__")),
    continueLoop(true),
    is_state(findstr(statestr)),
    is_transition(findstr(trstr)),
    is_initial(findstr(initstr)), 
    mainloopflag(true)
{
    targets[m_root->id] = m_root;
    pt = &targets;
    
}
Interpreter::~Interpreter()
{
}

bool Interpreter::parse()
{
    LOG4CXX_INFO(logger, "parsing XML file " << docname);
    pugi::xml_parse_result result = doc.load_file(docname.c_str());
    LOG4CXX_INFO(logger, "Load result: " << result.description());
    return result;
}

void Interpreter::buildmachine(std::string const & docfile)
{
    pugi::xml_node_iterator it;
    pugi::xml_node node; 
    pugi::xml_attribute attr; 

    docname = docfile;
    if (parse() == false)
    {
	std::cerr << "parse error\n";
	return;
    }

    for (node = doc.first_child(); node; node = node.next_sibling())
    {
	dig(node, m_root);
    }
    // look for document's initial state.

    node = doc.child("scxml");
    attr = node.attribute("initial");
    if (attr)
    {
	m_root->setInitial(attr.value());
	LOG4CXX_TRACE(logger, "document's initial to \"" 
		      << attr.value() <<"\"");
	// get default transition
	pugi::xml_node tr = node.child(TRANSITION_STR.c_str());
    }       
    // show me the machine.
    //tell(m_root);
}
  

TransitionTarget *Interpreter::parseStateNode(pugi::xml_node node,
					      TransitionTarget* parent)
{
    /*
      possible children ... from SCXML spec, 
      Currently supports only <initial> and <trasition> nodes.

      <onentry> Optional element holding executable content to be run             
      upon entering this <state>. Occurs 0 or more times.

      <onexit> Optional element holding executable content to be run
      when exiting this <state>. Occurs 0 or more times.
    
      <transition> Defines an outgoing transition from this
      state. Occurs 0 or more times.

      <initial> In states that have substates, an optional child which
      identifies the default initial state. Any transition which takes
      the parent state as its target will result in the statemachine
      also taking the transition contained inside the <initial>
      element. 

      <final>. Defines a final substate. Occurs 0 or more times. 

      <history> A child pseudo-state which records the descendant
      state(s) that the parent state was in the last time the system
      transitioned from the parent. May occur 0 or more times.

      <datamodel> Defines part or all of the datamodel. Occurs 0 or 1
      times. 

      <invoke> Invokes an external service. Occurs 0 or more times. 
    
      SKIPS <state> and <parallel>

      <state> Defines a sequential substate of the parent state. Occurs
      0 or more times.  
    
      <parallel> Defines a parallel substate. Occurs 0
      or more times. 

    */
    LOG4CXX_TRACE(logger,  "parse " << node.name()  << " id: " 
		  <<  ATTR_VALUE(node, "id") << " initial attr: " 
		  << ATTR_VALUE(node, INITIAL_STR.c_str()));
    TransitionTarget *state = factory.buildState(node, parent);
    LOG4CXX_TRACE(logger,  "adds " << state->id << " to targets")
    targets[state->id] = state;
    // Check initial attr.
    state->setInitial(ATTR_VALUE(node, INITIAL_STR.c_str()));

    pugi::xml_node_iterator it; 
    for(it=node.begin(); it != node.end(); ++it)
    {
	if (is_transition(*it))
	{
	    LOG4CXX_TRACE(logger, "Transition from " << state->id << " to " 
			  << ATTR_VALUE(*it, "target"));
	    Transition *t = 
		factory.buildTransition(state->id, 
					ATTR_VALUE(*it, "target"),
					ATTR_VALUE(*it, "event"),
					ATTR_VALUE(*it, "cond"));
	    state->transitions.push_back(*t);
	}
    }
    return state;
}

void Interpreter::dig(pugi::xml_node node, TransitionTarget* parent)
{
    pugi::xml_node_iterator it; 
    pugi::xml_attribute attr;
  
    for(it=node.begin(); it != node.end(); ++it)
    {
	if ( is_state(*it) )
	{
	    TransitionTarget* newstate = parseStateNode(*it, parent);
	    dig(*it, newstate);
	}
	else if (is_initial(*it))
	{
	    //cout << "node " << node.name() << " " << parent->id << endl;
	    // get default transition
	    pugi::xml_node tr = it->child(TRANSITION_STR.c_str());
	    //cout << "initial to " << ATTR_VALUE(tr,"target") << endl;
	    parent->setInitial(ATTR_VALUE(tr,"target"));
	}
	else
	    dig(*it, parent);
    }
}


void Interpreter::tell(TransitionTarget* node)
{
    TargetList::iterator it;
    TargetList::iterator jj;
    TransitionList::iterator tt;

    std::cout << "\nnode: " << node->id << endl;
    // " initial? " 
    // 	    <<dynamic_cast<State*>(node)->isInitial << std::endl;

    if (!node->children.empty())
    {
	cout << "\n children" << endl;
	for(jj=node->children.begin(); jj != node->children.end(); ++jj)
	    cout << "n: " << (*jj)->id << " ";
	cout << endl;
    }
    //tell(*it);
    // if (node->transitions.size())
    // {
    // 	std::cout << "Transitions" << std::endl;
    // 	for (tt=node->transitions.begin(); tt != node->transitions.end(); ++tt)
    // 	{
    // 	    std::for_each(tt->targetids.begin(), tt->targetids.end(), print);
    // 	}
    // }
  
    for (it=node->children.begin(); it != node->children.end(); ++it)
	tell(*it);
}

void Interpreter::run(void)
{
    TtMap::iterator jj;

    //startup(*m_root);	// set initial configuration.
    if (m_root->initialTransition.size())
    {
	strvec::iterator i;
	logSequence(m_root->initialTransition, "Initial Transitions");
	// for(i=m_root->initialTransition.begin(); i!=m_root->initialTransition.end();
	//     ++i)
	// {
	//     boost::scoped_ptr<Transition> t (new Transition(m_root->id, *i));
	//     execTransition(t.get());
	// }
    }

    // if (m_root->transitions.size())
    // {
    // 	cout << "Transitions \n";
    // 	TransitionList::iterator it;
    // 	cout << "Transitions state(s) (" << m_root->transitions.size() << ")\n";
    // 	for(it=m_root->transitions.begin(); it!=m_root->transitions.end(); ++it)
    // 	{
    // 	    std::cout << *it;
    // 	}
    // }

    previousConfiguration = configuration;
    configuration.clear();
    using namespace boost::lambda;
    TransitionList initial;
    strvec::iterator s;
    for(s=m_root->initialTransition.begin();
	s!= m_root->initialTransition.end(); ++s)
	initial.push_back( *factory.buildTransition(m_root->id, *s));

    enterStates(initial);

    LOG4CXX_INFO(logger, "START EVENT LOOP");
    startEventLoop();
}

void Interpreter::startEventLoop(void)
{
    bool initialStepComplete = false;
    LOG4CXX_TRACE(logger, "Enter " << __FUNCTION__);
    logSequence(configuration, "Config");
    while(! initialStepComplete)
    {
	TransitionList enabledTransitions = selectEventlessTransitions();

	LOG4CXX_TRACE(logger, "waiting for initial step");
	LOG4CXX_TRACE(logger, "empty enabled transitions?" << enabledTransitions.empty());
	logSequence(enabledTransitions, "enabled transitions ");

	if (enabledTransitions.empty())
	{
	    if (internalEventQueue.empty())
	    {
		initialStepComplete = true ;
		LOG4CXX_TRACE(logger, "initial step complete");
	    }
	    // XXX
	    // else
	    // {
	    // 	internalEvent = internalQueue.dequeue();
	    // 	datamodel["event"] = internalEvent;
	    // 	enabledTransitions = selectTransitions(internalEvent);
	    // }
	}
	if (! enabledTransitions.empty())
	{
	    microstep(0, enabledTransitions);
	    ;
	}
    }
    // XXX
	mainEventLoop();
}

TransitionList Interpreter::selectEventlessTransitions(void) 
{
    TransitionList enabledTransitions;
    strset::iterator it;

    LOG4CXX_TRACE(logger, "enter " <<  __FUNCTION__ );
    for (it = configuration.begin(); it != configuration.end(); ++it) 
    {
        TransitionTarget  *state = targets[*it];
        if (!isAtomic(state))
            continue;
        if (isPreempted(state, enabledTransitions))
            continue;
	TargetList lst, anc;
	//lst.push_back(state);
	lst = properAncestors(state, m_root);
	lst.push_front(state);
	/// XXX:
	//copy(anc.begin(), anc.end(), back_inserter(lst));

        bool found = false;
	TargetList::iterator j;
        for (j = lst.begin(); j!=lst.end() && !found; ++j) 
	{
	    TransitionTarget *s = *j;
            TransitionList transitions = s->transitions;
	    TransitionList::iterator k;

            for (k = transitions.begin(); k != transitions.end(); ++k) 
	    {
		if ( (*k).event == "" and (*k).cond == "")
		{
		    //LOG4CXX_TRACE(logger, "pick eventless TX from"  <<  (*k).sourceid << " to " << showSequence((*k).targetids));
		    enabledTransitions.push_back(*k);
		}
            }
        }
    }
    return enabledTransitions;
}



TransitionList Interpreter::selectTransitions(Event *event) 
{

    TransitionList enabledTransitions;
    strset::iterator it;
   
    LOG4CXX_TRACE(logger, "Enter " << __FUNCTION__ );
    LOG4CXX_TRACE(logger, "in evt: " << event->value);
    for (it = configuration.begin(); it != configuration.end(); ++it) 
    {
        TransitionTarget*  state = targets[*it];
        if (!isAtomic(state))
            continue;
        if (isPreempted(state, enabledTransitions))
            continue;
	TargetList lst, anc;
	//lst.push_back(state);
	lst = properAncestors(state, m_root);
	//copy(anc.begin(), anc.end(), back_inserter(lst));
	lst.push_front(state);
	
        bool found = false;
	TargetList::iterator j;
        for (j = lst.begin(); j !=lst.end() && !found; ++j) 
	{
	    TransitionTarget *s = *j;
            TransitionList transitions = s->transitions;
	    TransitionList::iterator k;
            for (k = transitions.begin(); k != transitions.end(); ++k) {
		Transition t = *k;
		cout << "event " << t.event << endl;
		if (t.event == event->value)
		{
		    // XXX: missing testing for transition's condition.
		    LOG4CXX_TRACE(logger, "add transition " << t);
		    enabledTransitions.push_back(t);
		    found = true;
		    break;
		}
		// XXX
//                 if (QAbstractTransitionPrivate::get(t)->callEventTest(event)) {
// #ifdef QSTATEMACHINE_DEBUG
//                     qDebug() << q << ": selecting transition" << t;
// #endif
//                     enabledTransitions.insert(t);
//                     found = true;
//                     break;
//                 }
            }
        }
    }
    return enabledTransitions;
}


void Interpreter::startup(TransitionTarget &p)
{
    TargetList::iterator jj;
    int count = 0;

    for(jj=p.children.begin(); jj != p.children.end(); ++jj)
    {
	startup(*(*jj));
	if ( (*jj)->start(configuration))
	    count +=1;
    }
    if (count && p.id != "__root__")
	configuration.insert(p.id);
  
    cout << "initial config\n";
    showSequence(configuration);
}

void Interpreter::execTransition(Transition *t)
{
    strvec::iterator i;
    TransitionTarget *dest;
    cout << __FUNCTION__ << endl;
    for (i=t->targetids.begin(); i!=t->targetids.end(); ++i)
    {
	dest = targets[*i];
	cout << "dest " << dest->id << endl;
	//dest->enter();
    }
}

/*
 
*/
void Interpreter::enterStates(TransitionList& enabledTransitions)
{
    TransitionList::iterator t;
    TransitionTarget *ancestor = 0;
    strset statesToEnter, statesForDefaultEntry;

    LOG4CXX_TRACE(logger,"ENTER " <<  __FUNCTION__);
    logSequence(enabledTransitions, "enabled transitions");

    for (t=enabledTransitions.begin(); t!=enabledTransitions.end(); ++t)
    {
	TransitionTarget *s = targets[(*t).sourceid];
	TargetList tstates;

	if ((*t).targetids.empty())
	    continue;

	findStates((*t).targetids, tstates);
	
	if ( (*t).type == Transition::INTERNAL)
	{
	    bool isancestor = true;
	    TargetList::iterator j;
	    for (j=tstates.begin(); j!=tstates.end(); ++j)
	    {
		isancestor = s->isAncestor(*j);
		if (isancestor == false)
		    break;
	    }
	    if (isancestor)
		ancestor = s;
	}
	else  
	{
	    // XXX: I disagree with this.
	     if (s)
		 tstates.push_front(s);
	     ancestor = findLCA(tstates);
	     if (s)
		 tstates.pop_front();
	}
	TargetList::iterator j;
	for (j = tstates.begin(); j!=tstates.end(); ++j)
	    addStatesToEnter(*j, statesToEnter, statesForDefaultEntry);
    }

    strset::iterator s;
    for (s=statesToEnter.begin(); s!=statesToEnter.end(); ++s)
     {
	 configuration.insert(targets[*s]->id);
	 if (targets[*s]->isFinal())
	     mainloopflag=false;
    // 	// process onentry
    // 	// emit signals ...
     }

    
    logSequence(statesToEnter, "states to enter");
    logSequence(statesForDefaultEntry, "states for default enter");
    logSequence(configuration, "machine configuration");
}

TargetList Interpreter::properAncestors(const TransitionTarget *state, 
					const TransitionTarget *upperBound)
{
    ASSERT(state != 0);
    TargetList result;
    TransitionTarget *s;
    for (s = state->parent.get(); s && s != upperBound; s = s->parent.get()) {
	result.push_back(s);
    }
    return result;
}


/*
  function findLCA(stateList):
  for anc in getProperAncestors(stateList.head(), null):
  if stateList.tail().every(lambda s: isDescendant(s,anc)):
  return anc
*/

TransitionTarget *Interpreter::findLCA( const TargetList &states)
{
    //unsigned int i;
    if (states.empty())
	return 0;
    cout << "findLCA " << states.size() << endl;
    showSequence(states);
    TargetList ancestors = properAncestors(states.front(), m_root);
    TargetList::iterator i;
    for (i = ancestors.begin(); i != ancestors.end(); ++i) 
    {
	TargetList::const_reverse_iterator j;
	TransitionTarget  *anc = *i;
	bool ok = true;
	for ( j = states.rbegin(); j !=states.rend() && ok; ++j) 
	{
	    TransitionTarget *s = *j;
	    if (!anc->isAncestor(s))
		ok = false;
	}
	if (ok)
	    return anc;
    }
    return m_root;
}

void Interpreter::addStatesToEnter(TransitionTarget *s, strset &statesToEnter,
				   strset &statesForDefaultEntry)
{
    ASSERT(s);
    logSequence(statesToEnter, "!states to enter");

    /// XXX: missing, support history.

    statesToEnter.insert(s->id);
    if (s->isParallel())
    {
	TargetList::iterator m;
	for(m = s->children.begin(); m != s->children.end(); ++m)
	    addStatesToEnter(*m, statesToEnter, statesForDefaultEntry);
    } else if (s->isCompound()) 
    {
	statesForDefaultEntry.insert(s->id);
	if (! s->initialTransition.empty())
	{
	    TargetList initial;
	    TargetList::iterator i;
	    
	    findStates(s->initialTransition, initial);
	     for(i=initial.begin(); i != initial.end(); ++i)
		 addStatesToEnter( *i, statesToEnter,  statesForDefaultEntry);
	     
	     // I'd prefer for_each.
	     // for_each(initial,
	     // 	     boost::bind(addStatesToEnter, _1, s, statesToEnter, 
	     // 			 statesForDefaultEntry));
	}	    
    }
}

bool Interpreter::isCompound(const TransitionTarget *s) 
{
    if (!s)
	return false;
    return s->type == TransitionTarget::Compound;

}

void Interpreter::findStates(strvec &t, TargetList &states)
{
    using namespace boost::lambda;
    ASSERT(! t.empty());
    std::transform(t.begin(), t.end(), 
      		   back_inserter(states), var(targets)[_1]);

#if 0
    cout << __FUNCTION__<< " " << t.size() << endl;
    strvec::iterator i;
    for (i=t.begin(); i != t.end(); ++i)
    {
	cout << "lookup " << *i << endl;
	cout << "tt " << targets[*i] << endl;
	states.push_back( targets[*i]);
    }
#endif
    return;
}


bool Interpreter::isPreempted(TransitionTarget *s, TransitionList &transitions)
{
    ASSERT(s!=0);

    LOG4CXX_TRACE(logger, "ENTER " << __FUNCTION__);
    LOG4CXX_TRACE(logger, "state " << s->id);
    cout << "Transitions: " << transitions.size() << endl;
    showSequence(transitions);
    TransitionList::iterator it;
    for (it = transitions.begin(); it != transitions.end(); ++it) {
        Transition t = *it;
	TargetList lst, targets;

	if (t.targetids.empty())
	    continue;
	findStates(t.targetids, targets);
	
	if (!targets.empty()) 
	{
	    lst.push_back(s);
	    lst.insert(lst.end(), targets.begin(), targets.end());
            TransitionTarget *lca = findLCA(lst);
	    if (lca && lca->isAncestor(s))
	    {
		LOG4CXX_TRACE(logger, __FUNCTION__
			      << " preempts selection of a transition from "
			      << s << "because " << s << " is a descendant of "
			      << lca);
                return true;
            }
        }
    }
    return false;
}

void Interpreter::mainEventLoop(void)
{
    LOG4CXX_INFO(logger, "MAIN LOOP");
    while (mainloopflag) {
        // if (stop) {
        //     stop = false;
        //     processing = false;
        //     stopProcessingReason = Stopped;
        //     break;
        // }
        TransitionList enabledTransitions;
        Event *e = new Event(); 
      
	enabledTransitions = selectTransitions(e);
        if (enabledTransitions.empty()) {
            delete e;
            e = 0;
        }

        if (enabledTransitions.empty() && ((e = dequeueInternalEvent()) != 0)) {
#ifdef QSTATEMACHINE_DEBUG
            qDebug() << q << ": dequeued internal event" << e << "of type" << e->type();
#endif
            enabledTransitions = selectTransitions(e);
            if (enabledTransitions.empty()) {
                delete e;
                e = 0;  
            }
        }

        if (enabledTransitions.empty()) {
            if ((e = dequeueExternalEvent()) != 0) {
		LOG4CXX_TRACE(logger, " dequeued external event " << e->value);
                enabledTransitions = selectTransitions(e);
                if (enabledTransitions.empty()) {
                    delete e;
                    e = 0;
                }
            } else {
                if (internalEventQueue.empty()) {
                    mainloopflag = false;
                    //stopProcessingReason = EventQueueEmpty;
                }
            }
        }
        if (!enabledTransitions.empty()) {
            //q->beginMicrostep(e);
	    microstep(e, enabledTransitions);
            //q->endMicrostep(e);
        }
        else 
	{
	    LOG4CXX_DEBUG(logger,  " no transitions enabled");
        }
        delete e;
    }
#ifdef QSTATEMACHINE_DEBUG
    qDebug() << q << ": finished the event processing loop";
#endif
    // switch (stopProcessingReason) {
    // case EventQueueEmpty:
    //     break;
    // case Finished:
    //     state = NotRunning;
    //     cancelAllDelayedEvents();
    //     unregisterAllTransitions();
    //     emit q->finished();
    //     break;
    // case Stopped:
    //     state = NotRunning;
    //     cancelAllDelayedEvents();
    //     unregisterAllTransitions();
    //     emit q->stopped();
    //     break;
    // }

}

void Interpreter::microstep(Event *event, TransitionList& enabledTransitions)
{
    strset newconfig;
    LOG4CXX_TRACE(logger, "ENTER " << __FUNCTION__);
    strset exitedStates = exitStates(event, enabledTransitions);
    logSequence(exitedStates, "states to exit");
    // XXX:
    //executeTransitionContent(event, enabledTransitions);
    set_difference(configuration.begin(), configuration.end(), 
		   exitedStates.begin(), exitedStates.end(), 
		   inserter(newconfig, newconfig.begin()));

    logSequence(newconfig, "new config");
    previousConfiguration = configuration;
    configuration = newconfig;
    enterStates(enabledTransitions);
}

/*
 
*/
strset Interpreter::exitStates(Event *event, TransitionList& enabledTransitions)
{
    TransitionList::iterator t;
    TransitionTarget *ancestor = 0;
    strset statesToExit;

    cout << __FUNCTION__ << " transitions:" << endl;
    showSequence(enabledTransitions);

    for (t=enabledTransitions.begin(); t!=enabledTransitions.end(); ++t)
    {
	TransitionTarget *s = targets[(*t).sourceid];
	TargetList tstates;

	if ((*t).targetids.empty())
	    continue;

	findStates((*t).targetids, tstates);
	
	if ( (*t).type == Transition::INTERNAL)
	{
	    bool isancestor = true;
	    TargetList::iterator j;
	    for (j=tstates.begin(); j!=tstates.end(); ++j)
	    {
		isancestor = s->isAncestor(*j);
		if (isancestor == false)
		    break;
	    }
	    if (isancestor)
		ancestor = s;
	}
	else
	{
	    if (s)
		tstates.push_back(s);
	    ancestor = findLCA(tstates);
	}

	strset::iterator j;
	for (j = configuration.begin(); j!=configuration.end(); ++j)
	    if (ancestor && ancestor->isAncestor(targets[*j]))
		statesToExit.insert(*j);
    }
    // XXX:
    //statesToExit = statesToExit.toList().sort(exitOrder)
    // for s in statesToExit:
    //     for h in s.history:
    //         if h.type == "deep":
    //             f = lambda s0: isAtomicState(s0) and isDescendant(s0,s) 
    //         else:
    //             f = lambda s0: s0.parent == s
    //         historyValue[h.id] = configuration.toList().filter(f)

    //cout << "States to exit: " << endl;
    logSequence(statesToExit, "states to exit");
//    TtSet::iterator j;
    //   for (j = statesToExit.begin(); j!=statesToExit.end(); ++j)
	// XXX: note, s=j
	//     for content in s.onexit:
	//         executeContent(content)
	//     for inv in s.invoke:
	//         cancelInvoke(inv)
	//configuration.erase(*j);
	;
    return statesToExit;
}

Event* Interpreter::dequeueExternalEvent(void)
{

    if (externalEventQueue.empty())
	return 0;
    
    LOG4CXX_TRACE(logger, "deque external");    
    Event* e = externalEventQueue.front();
    externalEventQueue.pop();
    return e;
};
